package 图.树;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/16 15:36
 */
public class CreateTree {

    /*
    练习一下 树的生成
    给出一个数组生成一个二叉树!

    给出的 数组的形式:
    ①: [1,2,null,5,null] 如果节点 为空 则为  null
    ②: [1,2,-1,5,-1] , -1 表示节点 为空
     */



    /*
     如果 递归 是这样 构建的 话, 那么 迭代,原理也一样呗
     */
    public TreeNode createTreeRecursion(int nums[],int index){
        if(index >= nums.length || nums[index] == -1){
            return null;
        }
        TreeNode root = new TreeNode(nums[index]);
        root.left = createTreeRecursion(nums,index * 2 + 1);// 向左子树构建
        root.right = createTreeRecursion(nums,index * 2 + 2);
        return root;
    }

    /*
     迭代
     思考一下, 这一种迭代方式, 和下面的 迭代方式的区别
     原来是 这样:
     下面这种方式, 不好构建的,还是需要用 队列 来辅助构建! (原来如此)
     */
    // failure version
    public TreeNode createTreeUnRecursion(int nums[]){
        if(nums.length == 0 || nums[0] == -1 || nums == null){
            return null;
        }
        TreeNode root = new TreeNode(nums[0]);
        for(int i = 0;i < nums.length;){
            int indexL = i * 2 + 1,indexR = i * 2 + 2;
            TreeNode left = indexL < nums.length && nums[indexL] != -1 ? new TreeNode(nums[indexL]) : null;
            TreeNode right = indexR < nums.length && nums[indexR] != -1 ? new TreeNode(nums[indexR]) : null;

        }
        return root;
    }


    public TreeNode createTree(int nums[]){
        Deque<TreeNode> queue = new ArrayDeque<>(nums.length);
        if(nums.length == 0 || nums[0] == -1 || nums == null){
            return null;
        }
        TreeNode root = new TreeNode(nums[0]);
        queue.addLast(root);
        int index = 1;
        /*
         下面 不用 index * 2 + 1 or index * 2 + 2 来找
         而是直接通过 index 一次 走两步,来找到 某个节点相应的子节点!
         */
        while(!queue.isEmpty()){
            TreeNode temp = queue.remove();
            if(index == nums.length){
                break;
            }
            if(nums[index] != -1){
                temp.left = new TreeNode(nums[index]);
                queue.addLast(temp.left);
            }
            index++;
            // 判断 右节点
            if(index == nums.length){
                break;
            }
            if(nums[index] != -1){
                temp.right = new TreeNode(nums[index]);
                queue.addLast(temp.right);
            }
            index++;

        }
        return root;
    }

// for test
    public void recursion(TreeNode root){
        if(root == null){
            return ;
        }
        recursion(root.left);
        recursion(root.right);
        System.out.print(root.val + " ");
    }

    @Test
    public void test(){
        int nums[] = {4,2,7,1,-1,6,-1};
        recursion(createTreeRecursion(nums,0));
        System.out.println();
        recursion(createTree(nums));
    }


    public static TreeNode stringToTreeNode(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return null;
        }

        String[] parts = input.split(",");
        String item = parts[0];
        TreeNode root = new TreeNode(Integer.parseInt(item));
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);

        int index = 1;
        while(!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int leftNumber = Integer.parseInt(item);
                node.left = new TreeNode(leftNumber);
                nodeQueue.add(node.left);
            }

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int rightNumber = Integer.parseInt(item);
                node.right = new TreeNode(rightNumber);
                nodeQueue.add(node.right);
            }
        }
        return root;
    }
}
